package com.yun.algorithm.dynamicprogramming;

import java.util.Arrays;


/**
 * 动态规划
 * 钢条切割问题
 */
public class CutRodProblem {
    /*
        0  1  2  3  4  5  6  7  8  9  10
        0  1  5  8  9  10 17 17 20 24 30
     */
    static int cut(int[] values, int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i < values.length; i++) {
            for (int j = i; j < n + 1; j++) {
                dp[j] = Math.max(dp[j], dp[j - i] + values[i]);
            }
            System.out.println(Arrays.toString(dp));
        }
        return 0;
    }

    public static void main(String[] args) {
        cut(new int[]{0, 1, 5, 8, 9}, 4);
    }
}
